This video is an Introductory lecture to Graph data structure.
This track of the course covers the topic "Graph".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Graphs.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video is an Introductory lecture to Graph data structure.
This video introduces us to the Graph Representation through Adjacency Matrix.
Codes:
This video introduces us to the Graph Representation through Adjacency List.
This video discusses the implementation of the Adjacency List in C++.
Code:
This video discusses the implementation of the Adjacency List in Java.
Code:
This video discusses the comparison of the Adjacency Matrix vs List in C++.
This video discusses the Breadth First Search algorithm in the graph.
We discuss following versions of B.F.S. :
1. Given an undirected graph and a source vertex 's' ,print B.F.S. from given source.
2. B.F.S on disconnected graphs.
3. Print number of islands in a graph (or number of connected components in a graph).
This video familiarises us with the Applications of Breadth-First Search in the world of the computer programming.
This video discusses the Depth First Search algorithm in a graph.
Codes:
This video throws light on various applications of Depth First Search algorithm.
Given an Unweighted Graph and a source point, the task is to find the shortest path between the source point and every other point in the graph.
Codes:
This problem discusses the Detection of a Cycle in an Undirected Graph.
Codes:
This problem discusses the Detection of a Cycle in an Undirected Graph using DFS.
Codes:
This video discusses the problem of Topological Sorting using Kahn's BFS Based Algorithm.
Codes:
This problem discusses the Detection of a Cycle in an Undirected Graph using Kahn's algorithm.
Codes:
This video discusses the Topological Sorting using the DFS Based Algorithm.
Codes:
This video discusses the problem of finding the Shortest Path in Directed Acyclic Graph.
Codes:
This video discusses the concept of Minimum Spanning Tree and how can it be calculated using Prims Algorithm.
This video explains the concept and working of the Dijkstra Shortest path Algorithm through a few working examples.
Kosaraju's Algorithm Part 1
Kosaraju's Algorithm Part 2
Codes:
Explanation of the algorithm and working of it for negative weight cycles.
Codes:
This video introduces us to the Articulation Point or the cut vertices. We will also be looking at a few problems where we will need to find the articulation point for a connected and undirected graph.
Codes:
This video introduces us to the bridge in a graph. It discusses the solution of finding the bridges in an undirected graph.
Codes:
This video discusses the Tarjan's Algorithm for finding the strongly connected components in a directed graph.
Codes:
In this video Kruskal's algorithm and its implementation using Disjoint Set Data Structure is discussed
Codes:
Directed and Undirected Graphs


Representing Graphs
Following two are the most commonly used representations of a graph:

Adjacency list of vertex 0
head -> 1-> 4
Adjacency list of vertex 1
head -> 0-> 2-> 3-> 4
Adjacency list of vertex 2
head -> 1-> 3
Adjacency list of vertex 3
head -> 1-> 2-> 4
Adjacency list of vertex 4
head -> 0-> 1-> 3










Since the Queue is empty now, it means that the complete graph is traversed.
1 2 3 4 5 6









Following is Depth First Traversal (starting from vertex 2)
2 0 1 3
Graph contains cycle
Given a graph and a source vertex in the graph, find the shortest paths from source to all vertices in the given graph.

1) Initialize distances of all vertices as infinite.
2) Create an empty priority_queue pq. Every item
of pq is a pair (weight, vertex). Weight (or
distance) is used as the first item of pair
as the first item is by default used to compare
two pairs
3) Insert source vertex into pq and make its
distance as 0.
4) While either pq doesn't become empty
a) Extract minimum distance vertex from pq.
Let the extracted vertex be u.
b) Loop through all adjacent of u and do
following for every vertex v.
// If there is a shorter path to v
// through u.
If dist[v] > dist[u] + weight(u, v)
(i) Update distance of v, i.e., do
dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the pq (Even if v is
already there)
5) Print distance array dist[] to print all shortest
paths.
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1

1) Initialize all vertices as not visited.
2) Do following for every vertex 'v'.
(a) If 'v' is not visited before, call DFSUtil(v)
(b) Print new line character
// This Function performs DFS traversal
// of vertex v.
DFSUtil(v)
1) Mark 'v' as visited.
2) Print 'v'
3) Do following for every adjacent 'u' of 'v'.
If 'u' is not visited, then recursively call DFSUtil(u)
Following are connected components
0 1 2
3 4
What is Minimum Spanning Tree?
Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.Prim's Algorithm
Prim’s algorithm is also a Greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
How to implement the above algorithm?
We use a boolean array mstSet[] to represent the set of vertices included in MST. If a value mstSet[v] is true, then vertex v is included in MST, otherwise not. Array key[] is used to store key values of all vertices. Another array parent[] to store indexes of parent nodes in MST. The parent array is the output array which is used to show the constructed MST.Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
How to find all articulation points in a given graph?
A simple approach is to one by one remove all vertices and see if removal of a vertex causes disconnected graph. Following are steps of a simple approach for the connected graph.
low[u] = min(disc[u], disc[w])
where w is an ancestor of u and there is a back edge from
some descendant of u to w.
Articulation points in first graph
0 3
Articulation points in second graph
1 2
Articulation points in third graph
1
How does this work?
The above algorithm is DFS based. It does DFS two times. DFS of a graph produces a single tree if all vertices are reachable from the DFS starting point. Otherwise, DFS produces a forest. So DFS of a graph with only one SCC always produces a tree. The important point to note is DFS may produce a tree or a forest when there are more than one SCCs depending upon the chosen starting point. For example, in the above diagram, if we start DFS from vertices 0 or 1 or 2, we get a tree as output. And if we start at 3 or 4, we get a forest. To find and print all SCCs, we would want to start DFS from vertex 4 (which is a sink vertex), then move to 3 which is sunk in the remaining set (set excluding 4) and finally any of the remaining vertices (0, 1, 2). So how do we find this sequence of picking vertices as starting points of DFS? Unfortunately, there is no direct way of getting this sequence. However, if we do a DFS of graph and store vertices according to their finish times, we make sure that the finish time of a vertex that connects to other SCCs (other than its own SCC), will always be greater than finish time of vertices in the other SCC (See this for proof). For example, in DFS of above example graph, the finish time of 0 is always greater than 3 and 4 (irrespective of the sequence of vertices considered for DFS). And the finish time of 3 is always greater than 4. DFS doesn't guarantee about other vertices, for example, finish times of 1 and 2 may be smaller or greater than 3 and 4 depending upon the sequence of vertices considered for DFS. So to use this property, we do DFS traversal of the complete graph and push every finished vertex to a stack. In stack, 3 always appears after 4, and 0 appear after both 3 and 4.
Following are strongly connected components in given graph
0 1 2
3
4
How to find all bridges in a given graph?
A simple approach is to one by one remove all edges and see if removal of an edge causes disconnected graph. Following are steps of a simple approach for a connected graph.Bridges in first graph
3 4
0 3
Bridges in second graph
2 3
1 2
0 1
Bridges in third graph
1 6
Input : mat[][] = {{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
Output : 5
Solution - The problem can be easily solved by applying DFS() on each component. In each DFS() call, a component or a sub-graph is visited. We will call DFS on the next un-visited component. The number of calls to DFS() gives the number of connected components. BFS can also be used. {1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
Pseudo Code
// A utility function to do DFS for a
// 2D boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(int M[][COL], int row, int col,
bool visited[][COL])
{
// These arrays are used to get
// row and column numbers of 8
// neighbours of a given cell
rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 }
colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 }
// Mark this cell as visited
visited[row][col] = true
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited)
}
// The main function that returns
// count of islands in a given boolean
// 2D matrix
int countIslands(int M[][COL])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL]
memset(visited, 0, sizeof(visited))
// Initialize count as 0 and
// travese through the all cells of
// given matrix
int count = 0
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
// If a cell with value 1 is not
if (M[i][j] && !visited[i][j]) {
// visited yet, then new island found
// Visit all cells in this island.
DFS(M, i, j, visited)
// and increment island count
++count
}
return count
}
// Utility function to check back edge in a directed graph
bool isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true
recStack[v] = true
// Recur for all the vertices adjacent to this vertex
list < int > :: iterator i
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true
else if (recStack[*i])
return true
}
}
recStack[v] = false; // remove the vertex from recursion stack
return false;
}
// Returns true if the graph contains a cycle, else false.
bool isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V]
bool *recStack = new bool[V]
for(int i = 0; i < V; i++)
{
visited[i] = false
recStack[i] = false
}
// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true
return false
}

// A recursive function used by topological sort
void topologicalSortUtil(int v, bool visited[],
stack&Stack)
{
// Mark the current node as visited.
visited[v] = true
// Recur for all the vertices adjacent to this vertex
list < int > :: iterator i
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
// Push current vertex to stack which stores result
Stack.push(v)
}
// The function to do Topological Sort. It uses recursive
// topologicalSortUtil()
void topologicalSort()
{
stack < int > Stack
// Mark all the vertices as not visited
bool *visited = new bool[V]
for (int i = 0; i < V; i++)
visited[i] = false
// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack)
// Print contents of stack
// Topological Order
while (Stack.empty() == false)
{
print(Stack.top())
Stack.pop()
}
}
0: Empty cellSo we have to determine what is the minimum time required so that all the oranges become rotten. A rotten orange at index [ i,j ] can rot other fresh orange at indexes [ i-1, j ], [ i+1, j ], [ i, j-1 ], [ i, j+1 ] (up, down, left and right). If it is impossible to rot every orange then simply return -1.
1: Cells have fresh oranges
2: Cells have rotten oranges
Input: arr[][C] = { {2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges can become rotten in 2 time frames.
Input: arr[][C] = { {2, 1, 0, 2, 1},
{0, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges cannot be rotten.
1) Create an empty Q.Pseudo Code
2) Find all rotten oranges and enqueue them to Q. Also enqueue a delimiter to indicate the beginning of next time frame.
3) While Q is not empty do following
....3.a) Do following while delimiter in Q is not reached
........ (i) Dequeue an orange from queue, rot all adjacent oranges. While rotting the adjacent, make sure that the time frame is incremented only once. And the time frame is not incremented if there are no adjacent oranges.
....3.b) Dequeue the old delimiter and enqueue a new delimiter. The oranges rotten in the previous time frame lie between the two delimiters.
// This function finds if it is possible to rot all oranges or not.
// If possible, then it returns minimum time required to rot all,
// otherwise returns -1
int rotOranges(int arr[][C])
{
// Create a queue of cells
queue < cell > Q
cell temp
ans = 0
// Store all the cells having rotten orange in first time frame
for (int i=0; i < R; i++)
{
for (int j=0; j < C; j++)
{
if (arr[i][j] == 2)
{
temp.x = i
temp.y = j
Q.push(temp)
}
}
}
// Separate these rotten oranges from the oranges which will rotten
// due the oranges in first time frame using delimiter which is (-1, -1)
temp.x = -1
temp.y = -1
Q.push(temp)
// Process the grid while there are rotten oranges in the Queue
while (!Q.empty())
{
// This flag is used to determine whether even a single fresh
// orange gets rotten due to rotten oranges in current time
// frame so we can increase the count of the required time.
bool flag = false
// Process all the rotten oranges in current time frame.
while (!isdelim(Q.front()))
{
temp = Q.front()
// Check right adjacent cell that if it can be rotten
if (isvalid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)
{
// if this is the first orange to get rotten, increase
// count and set the flag.
if (!flag) ans++, flag = true
// Make the orange rotten
arr[temp.x+1][temp.y] = 2
// push the adjacent orange to Queue
temp.x++
Q.push(temp)
temp.x-- // Move back to current cell
}
// Check left adjacent cell that if it can be rotten
if (isvalid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1) {
if (!flag) ans++, flag = true
arr[temp.x-1][temp.y] = 2
temp.x--
Q.push(temp) // push this cell to Queue
temp.x++
}
// Check top adjacent cell that if it can be rotten
if (isvalid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {
if (!flag) ans++, flag = true
arr[temp.x][temp.y+1] = 2
temp.y++
Q.push(temp) // Push this cell to Queue
temp.y--
}
// Check bottom adjacent cell if it can be rotten
if (isvalid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1) {
if (!flag) ans++, flag = true
arr[temp.x][temp.y-1] = 2
temp.y--
Q.push(temp) // push this cell to Queue
}
Q.pop()
}
// Pop the delimiter
Q.pop()
// If oranges were rotten in current frame than separate the
// rotten oranges using delimiter for the next frame for processing.
if (!Q.empty()) {
temp.x = -1
temp.y = -1
Q.push(temp)
}
// If Queue was empty than no rotten oranges left to process so exit
}
// Return -1 if all arranges could not rot, otherwise -1.
return (checkall(arr))? -1: ans
}
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
A | I and II |
B | III and IV |
C | IV only |
D | II and IV |